package com.work.leetcode.solution;

/**
 * Created by suk on 2020/4/19.
 */
class Solution {

    public static void main(String[] args) {
        /*-
        根据arr.length找到超过25%处的下标
        - 保持固定距离（25%个数）
        - 如若两个指针所指的数相等及为所求*/
//        int[] arr = {1,2,2,6,6,6,6,7,10};
//        int[] arr = {1, 2, 3, 3};
        int[] arr = {1, 2, 3, 4, 5, 5, 6};
        System.out.println(findSpecialInteger2(arr));
    }
    /* 有序数组中出现次数超过25%的元素 */
    public static int findSpecialInteger(int[] arr) {
        int len = arr.length/4;
        int count = 0;
        int initial = arr[0];
        if (arr.length == 1)
            return initial;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == initial) {
                if (++count > len)
                    return arr[i - 1];
            } else {
                count = 1;
                initial = arr[i];
            }

        }
        return -1;
    }

    public static int findSpecialInteger2(int[] arr) {
        int before = arr.length / 4;
        for(int i = 0; before < arr.length; i++, before++){
            if(arr[i] == arr[before]) return arr[i];
        }
        return arr[arr.length-1];

    }

    /**
     *假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/
     */
    public int climbStairs(int n) {
        int first = 1;
        int second = 2;
        if (n == 1)
            return 1;
        else {
            for (int i = 3; i <= n; i++) {
                int third = first + second;
                first = second;
                second = third;
            }
            return second;
        }
    }
}
